We address the problem of reaching consensus in the presence of Byzantinefaults. In particular, we are interested in investigating the impact ofmessages relay on the network connectivity for a correct iterative approximateByzantine consensus algorithm to exist. The network is modeled by a simpledirected graph. We assume a node can send messages to another node that is upto $l$ hops away via forwarding by the intermediate nodes on the routes, where$l\in \mathbb{N}$ is a natural number. We characterize the necessary andsufficient topological conditions on the network structure. The tightconditions we found are consistent with the tight conditions identified for$l=1$, where only local communication is allowed, and are strictly weaker for$l>1$. Let $l^*$ denote the length of a longest path in the given network. For$l\ge l^*$ and undirected graphs, our conditions hold if and only if $n\ge3f+1$ and the node-connectivity of the given graph is at least $2f+1$ , where$n$ is the total number of nodes and $f$ is the maximal number of Byzantinenodes; and for $l\ge l^*$ and directed graphs, our conditions is equivalent tothe tight condition found for exact Byzantine consensus. Our sufficiency is shown by constructing a correct algorithm, wherein thetrim function is constructed based on investigating a newly introduced minimalmessages cover property. The trim function proposed also works overmulti-graphs.
展开▼
机译：我们解决了在拜占庭式故障存在下达成共识的问题。尤其是，我们有兴趣调查消息中继对网络连接的影响，以找到正确的迭代近似拜占庭共识算法。网络由一个简单的有向图建模。我们假设一个节点可以通过路由上的中间节点进行转发，将消息发送到跳远$ l $的另一个节点，其中\ mathbb {N} $中的$ l \是自然数。我们描述了网络结构上必要和充分的拓扑条件。我们发现的严格条件与为$ l = 1 $所确定的严格条件一致，其中只允许本地通信，而对于严格的弱化条件（$ l> 1 $）。令$ l ^ * $表示给定网络中最长路径的长度。对于$ l \ ge l ^ * $和无向图，当且仅当$ n \ ge3f + 1 $且给定图的节点连接性至少为$ 2f + 1 $时，我们的条件成立，其中$ n $为节点总数，$ f $是拜占庭式节点的最大数目；对于$ l \ ge l ^ * $和有向图，我们的条件等效于为精确的拜占庭共识找到的紧条件。通过构造正确的算法来显示我们的充分性，其中，trim函数是基于对新引入的最小消息覆盖特性的研究而构造的。提出的修整函数也适用于多图。
展开▼
